package zuo.test8_ForceRecursive;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @Author: Forx
 * @Data: 2021/6/16
 * @Desc: Algorithm - zuo.test8_ForceRecursive
 * @Version: v1.0
 */
public class Mian {
    /**
     * 汉诺塔问题
     *
     * 解决这个问题,简单来说就是三步
     * 1-i-1 --> 中转站
     *   i   --> 终点
     * 1-i-1 --> 终点
     *
     * */
    public static void hanoi(int n){
        if (n>0){
            hanoiP(n,"left","right","other");
        }
    }
    public static void hanoiP(int i,String from,String to,String other){
        if(i==1){
            System.out.println("move\t" + i +"\t"+ from + "\tto\t" + to);
        }else {
            hanoiP(i-1,from,other,to);
            System.out.println("move\t" + i +"\t"+ from + "\tto\t" + to);
            hanoiP(i-1,other,to,from);
        }

    }

    public static void allSubStr(String string){
        char[] res = string.toCharArray();
        allSubStrP(res,0,new ArrayList<Character>());
    }
    public static void allSubStrP(char[] s, int i, List<Character> res){
        if(i==s.length){
            System.out.println(res);
        }else {
            List<Character> resKeep = copyList(res);
            resKeep.add(s[i]);
            allSubStrP(s,i+1,resKeep);
            List<Character> resNotKeep = copyList(res);
            allSubStrP(s,i+1,resNotKeep);
        }
    }
    public static List<Character> copyList(List<Character> in){
        ArrayList<Character> characters = new ArrayList<>();
        for(Character c: in){
            characters.add(c);
        }
        return characters;
    }

    public static void printAllStr(String str){
        if(str==null)return;
        char[] chars = str.toCharArray();
        ArrayList<String> res = new ArrayList<>();
        process(chars,0,res);
    }

    //str[0.i-1]范围上,是之前做的选择
    //请把所有的字符串形成的全排列,加入到res里去
    public static void process(char[] str,int i,ArrayList<String> res){
        if(i==str.length){
            res.add(String.valueOf(str));
            //System.out.println(res);
            return;
        }
        boolean[] visted = new boolean[26];
        for (int j = i; j < str.length; j++) {
            if(!visted[str[j]-'a']){
                visted[str[j]-'a'] = true;
                swap(str,i,j);//str[i..]范围上,所有的字符,都可以在i位置上,后续都去尝试
                process(str,i+1,res);
                swap(str,i,j);//恢复原来的字符串
            }
        }
    }
    public static void swap(char[] str, int i,int j){
        char c = str[i];
        str[i] = str[j];
        str[j] = c;
    }

    /**
     *
     * 给定一个整型数组arr,代表数值不同的纸牌排成一条线。玩家A和玩家B依次拿走每张纸
     * 牌,规定玩家A先拿,玩家B后拿,但是每个玩家每次只能拿走最左或最右的纸牌,玩家A
     * 和玩家B都绝顶聪明。请返回最后获胜者的分数。
     * 【举例】
     * arr=[1,2,100,4]
     * 开始时,玩家A只能拿走1或4。如果开始时玩家A拿走1,则排列变为[2,100,4],接下来
     * 玩家B可以拿走2或4,然后继续轮到玩家A
     * 如果开始时玩家A拿走4,则排列变为[1,2,100],接下来玩家B可以拿走1或100,然后继
     * 续轮到玩家A.
     * 玩家A作为绝顶聪明的人不会先拿4,因为拿4之后,玩家B将拿走100。所以玩家A会先拿1
     * 让排列变为[2,100,4],接下来玩家B不管怎么选,100都会被玩家A拿走。玩家A会获胜,
     * 分数为101。所以返回101。
     * arr=[1,100,2]
     * 开始时,玩家A不管拿1还是2,玩家B作为绝顶聪明的人,都会把100拿走。玩家B会获胜,
     * 分数为100。所以返回100。
     *
     * 没懂
     * */
    public static int playGame(int[] in){
        if(in==null)return -1;
        return Math.max(playGameP_firstHand(in,0,in.length-1),playGameP_secondHand(in,0,in.length-1));

    }
    public static int playGameP_firstHand(int[] in,int left,int right){
        if(left==right){
            return in[left];
        }
        return Math.max(in[left]+playGameP_secondHand(in,left+1,right)
                ,in[right] + playGameP_secondHand(in,left,right-1));
    }
    public static int playGameP_secondHand(int[] in,int left,int right){
        if(left==right){
            return 0;
        }
        return Math.min(playGameP_firstHand(in,left+1,right)
                ,playGameP_firstHand(in,left,right-1));
    }


    /**
     * 逆序一个栈
     *
     * */
    public static void reverseStack(Stack<Integer> stack){
        if(!stack.isEmpty())return;
        int i = getLastStack(stack);
        reverseStack(stack);
        stack.push(i);
    }

    public static int getLastStack(Stack<Integer> stack){
        int res = stack.pop();
        if(!stack.isEmpty()){
            int last = getLastStack(stack);
            stack.push(res);
            return last;
        }else {
            return res;
        }

    }
    /**
     * 规定1和A对应、2和B对应、3和C对应
     * 那么一个数字字符串比如”111",就可以转化为"AA"、"KA"和"AK
     * 给定一个只有数字字符组成的字符串str,返回有多少种转化结果。
     *
     * 相当于找所有子串,但是要加限制条件
     *
     * */

    public static int getMaxKinds(char[] str,int i){
        if(i==str.length){
            return 1;
        }
        if(str[i]=='0')return 0;
        if(str[i] == '1'){
            int res = getMaxKinds(str,i+1);
            if(i+1 < str.length){
                res+=getMaxKinds(str,i+2);
            }
            return res;
        }
        if(str[i] == '2'){
            int res = getMaxKinds(str,i+1);
            if(i+1 < str.length && (str[i+1]>='0' && str[i+1]<='6')){
                res+=getMaxKinds(str,i+2);
            }
            return res;
        }
        return getMaxKinds(str,i+1);
    }

    /**
     * 给定两个长度都为N的数组 we i ghts和 values, wei ghts[i和 values[i]分别代表
     * i号物品的重量和价值。给定一个正数bag,表示一个载重bag的袋子,你装的物
     * 品不能超过这个重量。返回你能装下最多的价值是多少?
     *
     * */

    public static int getBestWeight(int[] weights,int[] values,int i,int alreadyWeight,int bag){
        if(alreadyWeight>bag)return 0;
        if(i==weights.length)return 0;
        return Math.max(
                getBestWeight(weights,values,i+1,alreadyWeight,bag),
                values[i] + getBestWeight(weights,values,i+1,alreadyWeight+weights[i],bag)
        );

    }

    public static void main(String[] args) {
        //hanoi(4);
        allSubStr("abs");
    }


}
